package mess;

import javax.annotation.Resource;
import java.util.Arrays;

public class LeeCode_79 {
    public static void main(String[] args) {
        char[][] board = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        System.out.println(exist(board, "ABCCED"));
    }

    private static boolean exist(char[][] board, String word) {
        boolean[] res = new boolean[1];
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == word.charAt(0)){
                    boolean[][] used = new boolean[m][n];
                    used[i][j] = true;
                    backTrick(i, j, 0, board, word, used, m, n, res);
                }
            }
        }
        return res[0];
    }

    private static void backTrick(int i, int j, int index, char[][] board,
                                     String word, boolean[][] used, int m, int n, boolean[] res){
        if(index == word.length() - 1){
            res[0] = true;
            return;
        }
        char goal = word.charAt(index + 1);
        if(i - 1 >= 0 && !used[i - 1][j] && board[i - 1][j] == goal){
            boolean[][] newUsed = new boolean[m][n];
            for(int k = 0; k < m; k++){
                newUsed[k] = Arrays.copyOfRange(used[k], 0, n);
            }
            newUsed[i - 1][j] = true;
            backTrick(i - 1, j, index + 1, board, word, newUsed, m, n, res);
        }
        if(i + 1 >= 0 && i + 1 < m && !used[i + 1][j] && board[i + 1][j] == goal){
            boolean[][] newUsed = new boolean[m][n];
            for(int k = 0; k < m; k++){
                newUsed[k] = Arrays.copyOfRange(used[k], 0, n);
            }
            newUsed[i + 1][j] = true;
            backTrick(i + 1, j, index + 1, board, word, newUsed, m, n, res);
        }
        if(j - 1 >= 0 && !used[i][j - 1] && board[i][j - 1] == goal){
            boolean[][] newUsed = new boolean[m][n];
            for(int k = 0; k < m; k++){
                newUsed[k] = Arrays.copyOfRange(used[k], 0, n);
            }
            newUsed[i][j - 1] = true;
            backTrick(i, j - 1, index + 1, board, word, newUsed, m, n, res);
        }
        if(j + 1 >= 0 && j + 1 < n && !used[i][j + 1] && board[i][j + 1] == goal){
            boolean[][] newUsed = new boolean[m][n];
            for(int k = 0; k < m; k++){
                newUsed[k] = Arrays.copyOfRange(used[k], 0, n);
            }
            newUsed[i][j + 1] = true;
            backTrick(i, j + 1, index + 1, board, word, newUsed, m, n, res);
        }
    }
}
